package com.example.javabasic.suanfa.jiandan.三数之和;

import com.example.javabasic.suanfa.jiandan.快排.QuiteSort;
import org.apache.logging.log4j.util.EnglishEnums;
import org.checkerframework.checker.units.qual.A;

import java.util.*;

/**
 * @description 三数之和
 * @Author Lin FuYuan
 * @date 2021/4/30
 */
public class ThreeSum {

    public static void main(String[] args) {
//        int[] sum = {-1, 0, 1, 2, -1, -4};
        int[] sum = {1,-1,-1,0};
        //排序
        QuiteSort.stackSort(sum, 0, sum.length - 1);
        for (int i = 0; i < sum.length; i++) {
            System.out.print(sum[i]);
            System.out.print(" ");
        }
        System.out.println();
//        List<List<Integer>> lists1 = twoSum(sum, -2, 1);
//        System.out.println(lists1);


        List<List<Integer>> lists = threeSum2(sum);
        for (List<Integer> list : lists) {
            System.out.println(list);
        }



    }


    public static List<List<Integer>> threeSum(int[] nums, int result) {
        List<List<Integer>> data = new ArrayList<>();
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            //取第一个数
            int num1 = nums[i];
            if(set.contains(num1)){
                continue;
            }
            set.add(num1);
            //计算得第二个数和第三个数的和
            int sumTwo = result - num1;
            List<List<Integer>> lists = twoSum(nums, sumTwo, i);
            data.addAll(lists);
        }
        return data;
    }

    /**
     * @param nums 数组
     * @param sum  两数和
     * @param now  当前排除元素下标
     * @return java.util.List<java.lang.Integer>
     * @author Lin FuYuan
     * @date 2021/6/2
     */
    public static List<List<Integer>> twoSum(int[] nums, int sum, int now) {
        List<List<Integer>> list = new ArrayList<>();
        int a = now+1;
        int b = nums.length - 1;
        while (a < b) {
            int sum1 = nums[a] + nums[b];
            if (sum1 > sum) {
                b--;
            } else if (sum1 < sum) {
                a++;
            } else {
                List<Integer> li = new LinkedList<>();
                li.add(nums[now]);
                li.add(nums[a]);
                li.add(nums[b]);
                list.add(li);
                while(a<b&& nums[a] == nums[a+1]){
                    a++;
                }
                while(b>a && nums[b] == nums[b-1]){
                    b--;
                }
                a++;
                b--;
            }


        }
        return list;
    }



    public static List<List<Integer>> threeSum2(int[] nums){
        Arrays.sort(nums);
        List<List<Integer>> list = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if(nums[i]>0){
                break;
            }
            if(i-1>=0&& nums[i] == nums[i-1]){
                continue;
            }
            //两数之和
            int sum = 0- nums[i];
            int a = i+1;
            int b = nums.length-1;
            while(a<b){
                if(sum>nums[a]+nums[b]){
                    while(a<b&& nums[a] == nums[a+1]){
                        a++;
                    }
                    a++;
                }else if(sum<nums[a]+nums[b]){
                    while(b>a && nums[b] == nums[b-1]){
                        b--;
                    }
                    b--;
                }else{
                    List<Integer> li = new ArrayList<>();
                    li.add(nums[i]);
                    li.add(nums[a]);
                    li.add(nums[b]);
                    list.add(li);
                    while(a<b&& nums[a] == nums[a+1]){
                        a++;
                    }
                    while(b>a && nums[b] == nums[b-1]){
                        b--;
                    }
                    a++;
                    b--;
                }
            }


        }
        return list;
    }




}
